#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-10-22 9:51 上午
# @Author  : yangdy
# @File    : 2020-10-22.763.划分字母区间
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        if not S:
            return []
        m = {}
        for i in range(len(S)):
            if m.get(S[i]):
                m[S[i]][1] = i
            else:
                m[S[i]] = [i, i]
        # mm = list(map(lambda x: m[x], m))
        mm = []
        for x in range(26):
            key = chr(ord('a')+x)
            if m.get(key):
                mm.append(m[key])
        mm.sort(key=lambda x: x[0])
        ans, p = [0], -1
        for i in range(len(mm)):
            if mm[i][0] <= ans[-1]:
                if mm[i][1] > ans[-1]:
                    ans[-1] = mm[i][1]
            else:
                ans.append(mm[i][1])
        ans = list(map(lambda x: x+1, ans))
        for i in range(len(ans)-1, 0, -1):
            ans[i] -= ans[i-1]
        return ans


questions = [
    ("ababcbacadefegdehijhklij",),

]

work(questions, lambda q: Solution().partitionLabels(q[0]))

